package 剑指offer_leetcode;

import java.util.Arrays;

/**
 * JZ51数组中的逆序对
 */
public class 剑指Offer51_数组中的逆序对 {
    int cnt = 0;
    public int reversePairs(int[] nums) {
        if(nums.length==0)
            return 0;
        sort(nums);
        return cnt;
    }

    int[] sort(int[] nums){
        if(nums.length==1)
            return  nums;
        int mid = nums.length / 2;
        int[] leftNums = sort(Arrays.copyOfRange(nums,0,mid));
        int[] rightNums = sort(Arrays.copyOfRange(nums,mid,nums.length));
        return merge(leftNums,rightNums);
    }

    int[] merge(int[] leftNums, int[] rightNums){
        int[] res = new int[leftNums.length+rightNums.length];
        int left = 0 , right = 0 , p =0;
        while(left<leftNums.length && right<rightNums.length){
            if(leftNums[left]<=rightNums[right]){
                res[p++] = leftNums[left++];
            }else{
                res[p++] = rightNums[right++];
                cnt += (leftNums.length - left);
            }
        }
        while(left<leftNums.length)
            res[p++] = leftNums[left++];
        while(right<rightNums.length)
            res[p++] = rightNums[right++];

        return res;
    }
}
